package com.example.leetcode.c101_c200.c144;
/**
 * 给定一个二叉树，返回它的 前序 遍历。
 *
 *  示例:
 *
 * 输入: [1,null,2,3]
 *    1
 *     \
 *      2
 *     /
 *    3
 *
 * 输出: [1,2,3]
 * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import com.example.leetcode.common.TreeNode;
import com.example.leetcode.common.TreeNodeWrapper;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 二叉树的前序遍历
 * @author zhanpengguo
 * @date 2020-10-27 8:42
 */
public class Solution {

    List<Integer> ans = new ArrayList<>();

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                res.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return res;
    }

    private void digui(TreeNode root) {
        if (root == null) {
            return;
        }
        ans.add(root.val);
        digui(root.left);
        digui(root.right);
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode root = TreeNodeWrapper.stringToTreeNode("[1,2,3,null,4]");
        TreeNodeWrapper.prettyPrintTree(root);
        List<Integer> list = solution.preorderTraversal(root);
        System.out.println(list);
    }
}
